package cn.yuemouren.suanfa;

/**
 * @Author: Timi
 * @Description: 希尔排序
 * @Date: 2020/7/23 14:27
 */
public class HillSort {

    public static void main(String[] args) {

    }

    private static void sort(int[] arr){
        int dk = arr.length / 2;
        while(dk >= 1){
            sortInsert(arr,dk);
            dk = dk / 2;
        }
    }

    /**
     *
     * @param arr
     * @param dk 间隔
     */
    private static void sortInsert(int[] arr,int dk){

        for(int i = dk; i < arr.length; i++){
            //类似于插入排序，只是插入的变量值1，变成了dk
            while(arr[i] < arr[i - dk]){

                int j;
                int insertValue = arr[i];
                arr[i] = arr[i - dk];
                for(j = i - dk; j >= 0 && insertValue < arr[j]; j = j - dk)
                    arr[j + dk] = arr[j];
                arr[j + dk] = insertValue;
            }
        }
    }
}
